package 动态规划;
/**
 *   对这个 题 进行 思考 另外 一个 版本  
 *   从左上角 到达 右下角  有 obstacle 的 情况 下 
 *   的 最短 路径 
 *   （这又  回到 了 《射箭比赛 中的 最大 得分 问题 上面 》
 *   求 最大 得分  的 的 问题 了 这是  
 *   这类 题 好好 思考一下 该怎么 去做 ）
 *   
 *   对于 该题 还有 一个 点 就是  我是 用 数字 模拟的 下标 
 *   在 矩阵 行走的 
 * 用 两个 数字  形成的 下标 来模拟 这个 robot 的 行走 路径
 * 这也是 一种思想
 */
public class leetcode63不同路径机器人走路 {
	public static void main(String []args) {
		int [][]obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}};
		int n = obstacleGrid.length;
		int m = obstacleGrid[0].length;
		System.out.println(process(0,0,n,m,obstacleGrid));
		System.out.println(processOne(0,0,n,m,obstacleGrid));
		System.out.println(dp(n,m,obstacleGrid));
//		System.out.println(solution(0,0,3,3));
//		System.out.println(solutionDP(10,6));
//		System.out.println(solution(10,6));
//		long t1 = System.currentTimeMillis();
//		for(int i = 0 ;i < 1000000;i++) {
//			solutionDP(10,6);
//		}
//		long t2 = System.currentTimeMillis();
//		long t3 = System.currentTimeMillis();
//		for(int i = 0 ;i < 1000000;i++) {
//			solution(10,6);
//		}
//		long t4 = System.currentTimeMillis();
//		System.out.println(t2 - t1);
//		System.out.println(t4 - t3);
	}
	/**
	 * 这个 时候 再写  这个 机器人 
	 * 走 宫格 问题 跟 玩 似的 
	 * 进阶 版本 会有 四个方向
	 * {{1,0},{-1,0},{0,1}{0,-1}}
	 */
	static int dp(int n,int m,int [][] obstacle) {
		int  dp [][] = new int [n + 1][m + 1];
		dp [n - 1][m - 1] = 1;
		for(int i = n - 1;i >= 0;i--) {
			for(int  j = m - 1;j >= 0;j--) {
				if(i == n - 1 && j == m - 1 || obstacle[i][j] == 1)
					continue;
				dp [i][j] = dp[i + 1][j] + dp[i][j + 1];		
			}
		}
		return dp[0][0];
	}
	static int processOne(int x,int y,int n,int m,int [][] obstacle) {
		if(x == n - 1 && y == m - 1)
			return 1;
		if(x == n || y == m || obstacle[x][y] == 1)
			return  0;
		return processOne(x + 1,y,n,m,obstacle) + processOne(x ,y + 1,n,m,obstacle);
	}
	public static int process(int right,int down,int n,int m,int [][]obstacle) {
		/**
		 * 有趣的 现象  就是   这些 basecase 的  顺序 是很 重要 的 
		 * 一不小心 就会                数组越界  或者 死循环 
		 * 往往 一般  都可以 通过 basecase 的 顺序 调整 来 修改代码  
		 * basecase  这个 东西 很  奇妙的 说实话 
		 * 真的 细节 
		 */
			if(right == n || down == m) {
				return 0;
			}
			if(obstacle[right][down] == 1) {
				return 0;
			}
			/**
			 * 上面的  两个 if 可以 合成 一个 语句  对吧
			 * 可以合成 一个 if 语句 但是 要 注意 一点 就是 
			 * right == n || down == m 这条 boolean 表达式必须在 
			 * obstacle[right][down] 这个 Boolean 表达式 的 前面 否则 会产生 数组 越界  
			 * 的 异常  其实 这 想一下  也能明白 对吧 
			 */
			if(right == n - 1 && down == m - 1) {
				return 1;
			}
			int ans = 0 ;
			// forword right
			ans = process(right+1,down,n,m,obstacle);
//			forword  down
			ans += process(right,down + 1,n,m,obstacle);
			return ans;
	}
	/**
	 * 注意 这个 题 只有 向下 和 向 右 走 
	 * 之前写的 题 都是  向 四个方向 
	 * {{0,1}，{0,-1}，{1,0}，{-1,0}}
	 * 但是 对于 只有   两个 或者 一个 有限 个 方向的 话 就没有 必要  用 for 对吧
	 * 直接 枚举 就行了
	 */
	static int dir [][] = {{0,1},{1,0}};
	static int solution(int x,int y,int m,int n) {
		if(x == m -1 && y == n - 1) {
			return 1;
		}
		if(x == m || y == n) {
			return 0;
		}
		
		/**
		 * int ans = solution(x + 1,y,m,n);
		 * ans + = solution(x , y + 1,m,n );
		 * return ans;
		 * 
		 * 直接 把 代码  终极 集成
		 * return solution(x + 1,y,m,n) + solution(x,y + 1,n,m );
		 * 熟练 了 之后 就可以  直接 写成这样
		 * 因为 上面的 两组  代码就 没有任何 区别 对吧
		 */
		int ans = 0;
		for(int arr [] : dir) {
			ans += solution(x + arr[0],y + arr[1],m,n);
		}
	return ans;
	}
	
	static int solution(int m,int n) {
		int dp[][] = new int [m + 1][n + 1];
		dp[m - 1][n - 1] = 1;
		for(int i = m - 1; i >= 0; i--) {
			for(int  j = n -1 ;j >= 0;j--) {
				if(i == m -1 && j == n - 1)
					continue;
				int ans = 0;
				for(int arr[] : dir) {
					ans += dp[i + arr[0]][j + arr[1]];
				}
				dp[i][j] = ans;
			}
		}
		
		return dp[0][0];
	}
	static int solutionDP(int m,int n) {
		int dp [][] = new int [m + 1][n + 1];
		dp[m - 1][n - 1] = 1;
		for(int i = m -1;i >= 0; i--) {
			for(int j = n - 1;j >= 0;j--) {
				if(i == m -1 && j == n  - 1)
					continue;
				dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
			}
		}
		
		return dp[0][0];
	}
}
